Search Results

Documents authored by Kumar, Mrinal

Document
DOI: 10.4230/LIPIcs.ITCS.2024.27
Determinants vs. Algebraic Branching Programs

Authors: Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We show that for every homogeneous polynomial of degree d, if it has determinantal complexity at most s, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most O(d⁵s). Moreover, we show that for most homogeneous polynomials, the width of the resulting homogeneous ABP is just s-1 and the size is at most O(ds). Thus, for constant degree homogeneous polynomials, their determinantal complexity and ABP complexity are within a constant factor of each other and hence, a super-linear lower bound for ABPs for any constant degree polynomial implies a super-linear lower bound on determinantal complexity; this relates two open problems of great interest in algebraic complexity. As of now, super-linear lower bounds for ABPs are known only for polynomials of growing degree [Mrinal Kumar, 2019; Prerona Chatterjee et al., 2022], and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor [Mrinal Kumar and Ben Lee Volk, 2022]. While determinantal complexity and ABP complexity are classically known to be polynomially equivalent [Meena Mahajan and V. Vinay, 1997], the standard transformation from the former to the latter incurs a polynomial blow up in size in the process, and thus, it was unclear if a super-linear lower bound for ABPs implies a super-linear lower bound on determinantal complexity. In particular, a size preserving transformation from determinantal complexity to ABPs does not appear to have been known prior to this work, even for constant degree polynomials.
Cite as

Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk. Determinants vs. Algebraic Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ITCS.2024.27,
  author =	{Chatterjee, Abhranil and Kumar, Mrinal and Volk, Ben Lee},
  title =	{{Determinants vs. Algebraic Branching Programs}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.27},
  URN =		{urn:nbn:de:0030-drops-195550},
  doi =		{10.4230/LIPIcs.ITCS.2024.27},
  annote =	{Keywords: Determinant, Algebraic Branching Program, Lower Bounds, Singular Variety}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.44
If VNP Is Hard, Then so Are Equations for It

Authors: Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size. In a recent work of Chatterjee, Kumar, Ramya, Saptharishi and Tengse (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients do have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations.
Cite as

Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.STACS.2022.44,
  author =	{Kumar, Mrinal and Ramya, C. and Saptharishi, Ramprasad and Tengse, Anamay},
  title =	{{If VNP Is Hard, Then so Are Equations for It}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{44:1--44:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.44},
  URN =		{urn:nbn:de:0030-drops-158547},
  doi =		{10.4230/LIPIcs.STACS.2022.44},
  annote =	{Keywords: Computational Complexity, Algebraic Circuits, Algebraic Natural Proofs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.56
Ideal-Theoretic Explanation of Capacity-Achieving Decoding

Authors: Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithm. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and their encoding is the residue modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Univariate Multiplicity codes, while also capturing the less-studied Additive Folded Reed-Solomon codes as well as a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal-theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that good bounds on this distance lead to capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes.
Cite as

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan. Ideal-Theoretic Explanation of Capacity-Achieving Decoding. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 56:1-56:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhandari_et_al:LIPIcs.APPROX/RANDOM.2021.56,
  author =	{Bhandari, Siddharth and Harsha, Prahladh and Kumar, Mrinal and Sudan, Madhu},
  title =	{{Ideal-Theoretic Explanation of Capacity-Achieving Decoding}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{56:1--56:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.56},
  URN =		{urn:nbn:de:0030-drops-147499},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.56},
  annote =	{Keywords: List Decodability, List Decoding Capacity, Polynomial Ideal Codes, Multiplicity Codes, Folded Reed-Solomon Codes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.4
A Lower Bound on Determinantal Complexity

Authors: Mrinal Kumar and Ben Lee Volk

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The determinantal complexity of a polynomial P ∈ 𝔽[x₁, …, x_n] over a field 𝔽 is the dimension of the smallest matrix M whose entries are affine functions in 𝔽[x₁, …, x_n] such that P = Det(M). We prove that the determinantal complexity of the polynomial ∑_{i = 1}^n x_i^n is at least 1.5n - 3. For every n-variate polynomial of degree d, the determinantal complexity is trivially at least d, and it is a long standing open problem to prove a lower bound which is super linear in max{n,d}. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than max{n,d}, and improves upon the prior best bound of n + 1, proved by Alper, Bogart and Velasco [Jarod Alper et al., 2017] for the same polynomial.
Cite as

Mrinal Kumar and Ben Lee Volk. A Lower Bound on Determinantal Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2021.4,
  author =	{Kumar, Mrinal and Volk, Ben Lee},
  title =	{{A Lower Bound on Determinantal Complexity}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.4},
  URN =		{urn:nbn:de:0030-drops-142781},
  doi =		{10.4230/LIPIcs.CCC.2021.4},
  annote =	{Keywords: Determinantal Complexity, Algebraic Circuits, Lower Bounds, Singular Variety}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.9
A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits

Authors: Mrinal Kumar and Ben Lee Volk

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We show that there is an equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field 𝔽, there is a non-zero n²-variate polynomial P ∈ 𝔽[x_{1, 1}, …, x_{n, n}] of degree at most poly(n) such that every matrix M which can be written as a sum of a matrix of rank at most n/100 and a matrix of sparsity at most n²/100 satisfies P(M) = 0. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer and Landsberg [Fulvio Gesmundo et al., 2016] and improves the best upper bound known for this problem down from exp(n²) [Abhinav Kumar et al., 2014; Fulvio Gesmundo et al., 2016] to poly(n). We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices M such that the linear transformation represented by M can be computed by an algebraic circuit with at most n²/200 edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [Amir Shpilka and Ilya Volkovich, 2015] to construct low degree "universal" maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low degree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [Valentine Kabanets and Russell Impagliazzo, 2004].
Cite as

Mrinal Kumar and Ben Lee Volk. A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 9:1-9:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.ITCS.2021.9,
  author =	{Kumar, Mrinal and Volk, Ben Lee},
  title =	{{A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{9:1--9:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.9},
  URN =		{urn:nbn:de:0030-drops-135486},
  doi =		{10.4230/LIPIcs.ITCS.2021.9},
  annote =	{Keywords: Rigid Matrices, Linear Circuits, Degree Bounds, Circuit Lower Bounds}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.29
On Multilinear Forms: Bias, Correlation, and Tensor Rank

Authors: Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d.
Cite as

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar. On Multilinear Forms: Bias, Correlation, and Tensor Rank. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhrushundi_et_al:LIPIcs.APPROX/RANDOM.2020.29,
  author =	{Bhrushundi, Abhishek and Harsha, Prahladh and Hatami, Pooya and Kopparty, Swastik and Kumar, Mrinal},
  title =	{{On Multilinear Forms: Bias, Correlation, and Tensor Rank}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{29:1--29:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.29},
  URN =		{urn:nbn:de:0030-drops-126325},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.29},
  annote =	{Keywords: polynomials, Boolean functions, tensor rank, bias, correlation}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.2
A Quadratic Lower Bound for Algebraic Branching Programs

Authors: Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We show that any Algebraic Branching Program (ABP) computing the polynomial ∑_{i=1}^n xⁿ_i has at least Ω(n²) vertices. This improves upon the lower bound of Ω(nlog n), which follows from the classical result of Baur and Strassen [Volker Strassen, 1973; Walter Baur and Volker Strassen, 1983], and extends the results of Kumar [Mrinal Kumar, 2019], which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial. Our proof relies on a notion of depth reduction which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial ∑_{i=1}^n xⁿ_i can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial ∑_{i=1}^n xⁿ_i + ε(𝐱), for a structured "error polynomial" ε(𝐱). To complete the proof, we then observe that the lower bound in [Mrinal Kumar, 2019] is robust enough and continues to hold for all polynomials ∑_{i=1}^n xⁿ_i + ε(𝐱), where ε(𝐱) has the appropriate structure.
Cite as

Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A Quadratic Lower Bound for Algebraic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CCC.2020.2,
  author =	{Chatterjee, Prerona and Kumar, Mrinal and She, Adrian and Volk, Ben Lee},
  title =	{{A Quadratic Lower Bound for Algebraic Branching Programs}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{2:1--2:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.2},
  URN =		{urn:nbn:de:0030-drops-125546},
  doi =		{10.4230/LIPIcs.CCC.2020.2},
  annote =	{Keywords: Algebraic Branching Programs, Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.5
Lower Bounds for Matrix Factorization

Authors: Mrinal Kumar and Ben Lee Volk

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of lower bounds for algebraic circuits which compute linear transformations, matrix rigidity and data structure lower bounds. We first show, for every constant d, a deterministic construction in time exp(n^(1-Ω(1/d))) of a family {M_n} of n × n matrices which cannot be expressed as a product M_n = A_1 ⋯ A_d where the total sparsity of A_1,…,A_d is less than n^(1+1/(2d)). In other words, any depth-d linear circuit computing the linear transformation M_n⋅ 𝐱 has size at least n^(1+Ω(1/d)). This improves upon the prior best lower bounds for this problem, which are barely super-linear, and were obtained by a long line of research based on the study of super-concentrators (albeit at the cost of a blow up in the time required to construct these matrices). We then outline an approach for proving improved lower bounds through a certain derandomization problem, and use this approach to prove asymptotically optimal quadratic lower bounds for natural special cases, which generalize many of the common matrix decompositions.
Cite as

Mrinal Kumar and Ben Lee Volk. Lower Bounds for Matrix Factorization. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2020.5,
  author =	{Kumar, Mrinal and Volk, Ben Lee},
  title =	{{Lower Bounds for Matrix Factorization}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.5},
  URN =		{urn:nbn:de:0030-drops-125578},
  doi =		{10.4230/LIPIcs.CCC.2020.5},
  annote =	{Keywords: Algebraic Complexity, Linear Circuits, Matrix Factorization, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.14
Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't

Authors: Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric functions, in Representation theory [Stanley, 1999], in Schubert calculus [Ledoux and Malham, 2010] as well as in Enumerative combinatorics [Gasharov, 1996; Stanley, 1984; Stanley, 1999]. In recent years, they have also shown up in various incarnations in Computer Science, e.g, Quantum computation [Hallgren et al., 2000; Ryan O'Donnell and John Wright, 2015] and Geometric complexity theory [Ikenmeyer and Panova, 2017]. However, unlike some other families of symmetric polynomials like the Elementary Symmetric polynomials, the Power Symmetric polynomials and the Complete Homogeneous Symmetric polynomials, the computational complexity of syntactically computing Schur polynomials has not been studied much. In particular, it is not known whether Schur polynomials can be computed efficiently by algebraic formulas. In this work, we address this question, and show that unless every polynomial with a small algebraic branching program (ABP) has a small algebraic formula, there are Schur polynomials that cannot be computed by algebraic formula of polynomial size. In other words, unless the algebraic complexity class VBP is equal to the complexity class VF, there exist Schur polynomials which do not have polynomial size algebraic formulas. As a consequence of our proof, we also show that computing the determinant of certain generalized Vandermonde matrices is essentially as hard as computing the general symbolic determinant. To the best of our knowledge, these are one of the first hardness results of this kind for families of polynomials which are not multilinear. A key ingredient of our proof is the study of composition of well behaved algebraically independent polynomials with a homogeneous polynomial, and might be of independent interest.
Cite as

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan. Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 14:1-14:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chaugule_et_al:LIPIcs.CCC.2020.14,
  author =	{Chaugule, Prasad and Kumar, Mrinal and Limaye, Nutan and Mohapatra, Chandra Kanta and She, Adrian and Srinivasan, Srikanth},
  title =	{{Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{14:1--14:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.14},
  URN =		{urn:nbn:de:0030-drops-125660},
  doi =		{10.4230/LIPIcs.CCC.2020.14},
  annote =	{Keywords: Schur polynomial, Jacobian, Algebraic independence, Generalized Vandermonde determinant, Taylor expansion, Formula complexity, Lower bound}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.78
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

Authors: Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a depth-4 syntactically multilinear (Sigma Pi Sigma Pi) circuit of size at most exp ({O (sqrt{n log n})}). For degree d = omega(n/log n), this improves upon the upper bound of exp ({O(sqrt{d}log n)}) obtained by Tavenas [Sébastien Tavenas, 2015] for general circuits, and is known to be asymptotically optimal in the exponent when d < n^{epsilon} for a small enough constant epsilon. Our upper bound matches the lower bound of exp ({Omega (sqrt{n log n})}) proved by Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009], and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree. More generally, we show that an n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear circuit of product-depth Delta of size at most exp inparen{O inparen{Delta * (n/log n)^{1/Delta} * log n}}. It follows from the lower bounds of Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009] that in general, for constant Delta, the exponent in this upper bound is tight and cannot be improved to o inparen{inparen{n/log n}^{1/Delta}* log n}.
Cite as

Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.ICALP.2019.78,
  author =	{Kumar, Mrinal and Oliveira, Rafael and Saptharishi, Ramprasad},
  title =	{{Towards Optimal Depth Reductions for Syntactically Multilinear Circuits}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{78:1--78:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.78},
  URN =		{urn:nbn:de:0030-drops-106548},
  doi =		{10.4230/LIPIcs.ICALP.2019.78},
  annote =	{Keywords: arithmetic circuits, multilinear circuits, depth reduction, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.11
Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

Authors: Noga Alon, Mrinal Kumar, and Ben Lee Volk

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We prove a lower bound of Omega(n^2/log^2 n) on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial f(x_1, ..., x_n). Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff ([Ran Raz et al., 2008]), who proved a lower bound of Omega(n^{4/3}/log^2 n) for the same polynomial. Our improvement follows from an asymptotically optimal lower bound for a generalized version of Galvin's problem in extremal set theory.
Cite as

Noga Alon, Mrinal Kumar, and Ben Lee Volk. Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.CCC.2018.11,
  author =	{Alon, Noga and Kumar, Mrinal and Volk, Ben Lee},
  title =	{{Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.11},
  URN =		{urn:nbn:de:0030-drops-88799},
  doi =		{10.4230/LIPIcs.CCC.2018.11},
  annote =	{Keywords: Algebraic Complexity, Multilinear Circuits, Circuit Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.13
Hardness vs Randomness for Bounded Depth Arithmetic Circuits

Authors: Chi-Ning Chou, Mrinal Kumar, and Noam Solomon

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
In this paper, we study the question of hardness-randomness tradeoffs for bounded depth arithmetic circuits. We show that if there is a family of explicit polynomials {f_n}, where f_n is of degree O(log^2n/log^2 log n) in n variables such that f_n cannot be computed by a depth Delta arithmetic circuits of size poly(n), then there is a deterministic sub-exponential time algorithm for polynomial identity testing of arithmetic circuits of depth Delta-5. This is incomparable to a beautiful result of Dvir et al.[SICOMP, 2009], where they showed that super-polynomial lower bounds for depth Delta circuits for any explicit family of polynomials (of potentially high degree) implies sub-exponential time deterministic PIT for depth Delta-5 circuits of bounded individual degree. Thus, we remove the "bounded individual degree" condition in the work of Dvir et al. at the cost of strengthening the hardness assumption to hold for polynomials of low degree. The key technical ingredient of our proof is the following property of roots of polynomials computable by a bounded depth arithmetic circuit : if f(x_1, x_2, ..., x_n) and P(x_1, x_2, ..., x_n, y) are polynomials of degree d and r respectively, such that P can be computed by a circuit of size s and depth Delta and P(x_1, x_2, ..., x_n, f) equiv 0, then, f can be computed by a circuit of size poly(n, s, r, d^{O(sqrt{d})}) and depth Delta + 3. In comparison, Dvir et al. showed that f can be computed by a circuit of depth Delta + 3 and size poly(n, s, r, d^{t}), where t is the degree of P in y. Thus, the size upper bound in the work of Dvir et al. is non-trivial when t is small but d could be large, whereas our size upper bound is non-trivial when d is small, but t could be large.
Cite as

Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Hardness vs Randomness for Bounded Depth Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chou_et_al:LIPIcs.CCC.2018.13,
  author =	{Chou, Chi-Ning and Kumar, Mrinal and Solomon, Noam},
  title =	{{Hardness vs Randomness for Bounded Depth Arithmetic Circuits}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.13},
  URN =		{urn:nbn:de:0030-drops-88765},
  doi =		{10.4230/LIPIcs.CCC.2018.13},
  annote =	{Keywords: Algebraic Complexity, Polynomial Factorization Circuit Lower Bounds, Polynomial Identity Testing}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.19
A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs

Authors: Mrinal Kumar

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex s, and end vertex t and each edge having a weight which is an affine form in variables x_1, x_2, ..., x_n over an underlying field. An ABP computes a polynomial in a natural way, as the sum of weights of all paths from s to t, where the weight of a path is the product of the weights of the edges in the path. An ABP is said to be homogeneous if the polynomial computed at every vertex is homogeneous. In this paper, we show that any homogeneous algebraic branching program which computes the polynomial x_1^n + x_2^n + ... + x_n^n has at least Omega(n^2) vertices (and edges). To the best of our knowledge, this seems to be the first non-trivial super-linear lower bound on the number of vertices for a general homogeneous ABP and slightly improves the known lower bound of Omega(n log n) on the number of edges in a general (possibly non-homogeneous) ABP, which follows from the classical results of Strassen (1973) and Baur--Strassen (1983). On the way, we also get an alternate and unified proof of an Omega(n log n) lower bound on the size of a homogeneous arithmetic circuit (follows from [Strassen, 1973] and [Baur-Strassen, 1983]), and an n/2 lower bound (n over reals) on the determinantal complexity of an explicit polynomial [Mignon-Ressayre, 2004], [Cai, Chen, Li, 2010], [Yabe, 2015]. These are currently the best lower bounds known for these problems for any explicit polynomial, and were originally proved nearly two decades apart using seemingly different proof techniques.
Cite as

Mrinal Kumar. A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kumar:LIPIcs.CCC.2017.19,
  author =	{Kumar, Mrinal},
  title =	{{A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.19},
  URN =		{urn:nbn:de:0030-drops-75134},
  doi =		{10.4230/LIPIcs.CCC.2017.19},
  annote =	{Keywords: algebraic branching programs, arithmetic circuits, determinantal complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.31
An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields

Authors: Mrinal Kumar and Ramprasad Saptharishi

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
In this paper, we show exponential lower bounds for the class of homogeneous depth-5 circuits over all small finite fields. More formally, we show that there is an explicit family {P_d} of polynomials in VNP, where P_d is of degree d in n = d^{O(1)} variables, such that over all finite fields GF(q), any homogeneous depth-5 circuit which computes P_d must have size at least exp(Omega_q(sqrt{d})). To the best of our knowledge, this is the first super-polynomial lower bound for this class for any non-binary field. Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [Gupta et al., Fournier et al., Kayal et al., Kumar-Saraf] and for non-homogeneous depth-3 circuits over finite fields [Grigoriev-Karpinski, Grigoriev-Razborov]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from GF(q)^n to GF(q) as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lower bound of Kumar and Saraf [Kumar-Saraf].
Cite as

Mrinal Kumar and Ramprasad Saptharishi. An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 31:1-31:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2017.31,
  author =	{Kumar, Mrinal and Saptharishi, Ramprasad},
  title =	{{An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{31:1--31:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.31},
  URN =		{urn:nbn:de:0030-drops-75142},
  doi =		{10.4230/LIPIcs.CCC.2017.31},
  annote =	{Keywords: arithmetic circuits, lower bounds, separations, depth reduction}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.38
Finer Separations Between Shallow Arithmetic Circuits

Authors: Mrinal Kumar and Ramprasad Saptharishi

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
In this paper, we show that there is a family of polynomials P_n, where P_n is a polynomial in n variables of degree at most d = O(log^2(n)), such that * P_n can be computed by linear sized homogeneous depth-5 arithmetic circuits, * P_n can be computed by poly(n) sized non-homogeneous depth-3 arithmetic circuits. * Any homogeneous depth-4 arithmetic circuit computing P_n must have size at least n^{Omega(sqrt(d))}. This shows that the parameters for the depth reduction results of [Agrawal-Vinay 08, Koiran 12, Tavenas 13] are tight for extremely restricted classes of arithmetic circuits, for instance homogeneous depth-5 circuits and non-homogeneous depth-3 circuits, and over an appropriate range of parameters, qualitatively improve a result of [Kumar-Saraf 14], which showed that the parameters of depth reductions are optimal for algebraic branching programs. As an added advantage, our proofs are much shorter and simpler than the two known proofs of n^{Omega(sqrt(d))} lower bound for homogeneous depth-4 circuits [Kayal-Limaye-Saha-Srinivasan 14, Kumar-Saraf 14], albeit our proofs only work when d = O(log^2(n)).
Cite as

Mrinal Kumar and Ramprasad Saptharishi. Finer Separations Between Shallow Arithmetic Circuits. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 38:1-38:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.FSTTCS.2016.38,
  author =	{Kumar, Mrinal and Saptharishi, Ramprasad},
  title =	{{Finer Separations Between Shallow Arithmetic Circuits}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{38:1--38:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.38},
  URN =		{urn:nbn:de:0030-drops-68730},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.38},
  annote =	{Keywords: arithmetic circuits, lower bounds, separations, depth reduction}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.33
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity

Authors: Michael A. Forbes, Mrinal Kumar, and Ramprasad Saptharishi

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We say that a circuit C over a field F {functionally} computes a polynomial P in F[x_1, x_2, ..., x_n] if for every x in {0,1}^n we have that C(x) = P(x). This is in contrast to syntactically computing P, when C = P as formal polynomials. In this paper, we study the question of proving lower bounds for homogeneous depth-3 and depth-4 arithmetic circuits for functional computation. We prove the following results: 1. Exponential lower bounds for homogeneous depth-3 arithmetic circuits for a polynomial in VNP. 2. Exponential lower bounds for homogeneous depth-4 arithmetic circuits with bounded individual degree for a polynomial in VNP. Our main motivation for this line of research comes from our observation that strong enough functional lower bounds for even very special depth-4 arithmetic circuits for the Permanent imply a separation between #P and ACC0. Thus, improving the second result to get rid of the bounded individual degree condition could lead to substantial progress in boolean circuit complexity. Besides, it is known from a recent result of Kumar and Saptharishi [Kumar/Saptharishi, ECCC 2015] that over constant sized finite fields, strong enough {average case} functional lower bounds for homogeneous depth-4 circuits imply superpolynomial lower bounds for homogeneous depth-5 circuits. Our proofs are based on a family of new complexity measures called shifted evaluation dimension, and might be of independent interest.
Cite as

Michael A. Forbes, Mrinal Kumar, and Ramprasad Saptharishi. Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{forbes_et_al:LIPIcs.CCC.2016.33,
  author =	{Forbes, Michael A. and Kumar, Mrinal and Saptharishi, Ramprasad},
  title =	{{Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.33},
  URN =		{urn:nbn:de:0030-drops-58266},
  doi =		{10.4230/LIPIcs.CCC.2016.33},
  annote =	{Keywords: boolean circuits, arithmetic circuits, lower bounds, functional computation}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.34
Arithmetic Circuits with Locally Low Algebraic Rank

Authors: Mrinal Kumar and Shubhangi Saraf

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
In recent years there has been a flurry of activity proving lower bounds for homogeneous depth-4 arithmetic circuits, which has brought us very close to statements that are known to imply VP != VNP. It is a big question to go beyond homogeneity, and in this paper we make progress towards this by considering depth-4 circuits of low algebraic rank, which are a natural extension of homogeneous depth-4 arithmetic circuits. A depth-4 circuit is a representation of an N-variate, degree n polynomial P as P = sum_{i=1}^T Q_{i1} * Q_{i2} * ... * Q_{it} where the Q_{ij} are given by their monomial expansion. Homogeneity adds the constraint that for every i in [T], sum_{j} degree(Q_{ij}) = n. We study an extension where, for every i in [T], the algebraic rank of the set of polynomials {Q_{i1}, Q_{i2}, ... ,Q_{it}} is at most some parameter k. We call this the class of spnew circuits. Already for k=n, these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular t<=n (and hence k<=n). We study lower bounds and polynomial identity tests for such circuits and prove the following results. 1. Lower bounds: We give an explicit family of polynomials {P_n} of degree n in N = n^{O(1)} variables in VNP, such that any spnewn circuit computing P_n has size at least exp{(Omega(sqrt(n)*log(N)))}. This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for homogeneous depth-4 circuits [KLSS14, KS-full] as well as the Jacobian based lower bounds of Agrawal et al. which worked for spnew circuits in the restricted setting where T * k <= n. 2. Hitting sets: Let spnewbounded be the class of spnew circuits with bottom fan-in at most d. We show that if d and k are at most poly(log(N)), then there is an explicit hitting set for spnewbounded circuits of size quasipolynomial in N and the size of the circuit. This strengthens a result of Forbes which showed such quasipolynomial sized hitting sets in the setting where d and t are at most poly(log(N)). A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), upto a translation, every polynomial in a set of algebraically dependent polynomials can be written as a function of the polynomials in the transcendence basis. We believe this may be of independent interest. We combine this with shifted partial derivative based methods to obtain our final results.
Cite as

Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 34:1-34:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2016.34,
  author =	{Kumar, Mrinal and Saraf, Shubhangi},
  title =	{{Arithmetic Circuits with Locally Low Algebraic Rank}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{34:1--34:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.34},
  URN =		{urn:nbn:de:0030-drops-58288},
  doi =		{10.4230/LIPIcs.CCC.2016.34},
  annote =	{Keywords: algebraic independence, arithmetic circuits, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.35
Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing

Authors: Mrinal Kumar and Shubhangi Saraf

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form P = sum_{i=1}^T prod_{j=1}^d Q_{ij} such that each Q_{ij} is an arbitrary polynomial that depends on at most s variables. We prove the following results. 1. Over fields of characteristic zero, for every constant mu such that 0<=mu<=1, we give an explicit family of polynomials {P_{N}}, where P_{N} is of degree n in N = n^{O(1)} variables, such that any representation of the above type for P_{N} with s = N^{mu} requires Td >= n^{Omega(sqrt(n))}. This strengthens a recent result of Kayal and Saha [Kayal/Saha, ECCC 2014] which showed similar lower bounds for the model of sums of products of linear forms in few variables. It is known that any asymptotic improvement in the exponent of the lower bounds (even for s=sqrt(n)) would separate VP and VNP [Kayal/Saha, ECCC 2014]. 2. We obtain a deterministic subexponential time blackbox polynomial identity testing (PIT) algorithm for circuits computed by the above model when T and the individual degree of each variable in P are at most log^{O(1)}(N) and s<=N^{mu} for any constant mu<1/2. We get quasipolynomial running time when s<log^{O(1)}(N). The PIT algorithm is obtained by combining our lower bounds with the hardness-randomness tradeoffs developed in [Dvir/Shpilka/Yehudayoff, SIAM J. Comp. 2009; Kabanets/Impagliazzo, Comp. Compl. 2004]. To the best of our knowledge, this is the first nontrivial PIT algorithm for this model (even for the case s=2), and the first nontrivial PIT algorithm obtained from lower bounds for small depth circuits.
Cite as

Mrinal Kumar and Shubhangi Saraf. Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 35:1-35:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2016.35,
  author =	{Kumar, Mrinal and Saraf, Shubhangi},
  title =	{{Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{35:1--35:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.35},
  URN =		{urn:nbn:de:0030-drops-58270},
  doi =		{10.4230/LIPIcs.CCC.2016.35},
  annote =	{Keywords: arithmetic circuits, lower bounds, polynomial identity testing, hardness vs randomness}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact